1. Technical Field
The present disclosure relates to a method for improving data processing in general and, in particular, to a method of implementing a pseudo Least Recently Used (LRU) mechanism in a cache memory within a data processing system. Still more particularly, the present disclosure relates to a method for implementing a pseudo LRU mechanism in a four-way cache memory within a data processing system.
2. Description of the Prior Art
A data processing system typically includes both a system memory and a cache memory. A cache memory is a small and relatively high-speed memory interposed between a processor and the system memory. Information such as data or instructions may be copied from a portion of the system memory into the cache memory so that the information will be available to the processor in a relatively short amount of time when the requested information resides in the cache memory.
However, if the information requested by the processor cannot be found in the cache memory (i.e., a cache miss), the requested information must be obtained from the system memory. After the information has been obtained from the system memory, a copy of the information may also be placed in the cache memory for future usage, in addition to the immediate usage by the processor. Thus, when all possible storage locations for the information within the cache memory are completely filled, some of the information already stored in the cache memory has to be replaced by the new information via an operation known as linefill. Needless to say, it is important to have a strategy to decide what specific information already stored in the cache memory needs to be discarded in order to make room for the new information. Generally speaking, usually either a Least Recently Used (LRU) or a pseudo LRU strategy is employed to select a cache line of information to be replaced when a cache miss occurs. This is because statistical data has shown that for low associativity caches (caches that are configured as four-way set associative or less), an LRU type of replacement scheme can best minimize the cache miss ratio when compared to other cache replacement schemes such as random replacement or round-robin. The present disclosure provides a method for implementing a pseudo LRU cache replacement mechanism with fewer bits than prior art implementations.